package leetcode.year2021.month9;


public class _24_01LinkedListCenterNode876 {
  public static void main(String[] args) {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;

    System.out.println(middleNode(node1));
  }

  public static ListNode middleNode(ListNode head) {
    // 先计算链表的长度
    ListNode headNode = head;
    ListNode resultNode = head;
    int resultIndex = 1;
    int count = 1;
    while (headNode.next != null) {
      headNode = headNode.next;
      count++;
    }

    resultIndex = count / 2 + 1;

    while (resultIndex > 1){
      resultNode = resultNode.next;
      resultIndex--;
    }

    return resultNode;
  }

  public static class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }

  /**
   * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
   *
   * 如果有两个中间结点，则返回第二个中间结点。
   *
   *  
   *
   * 示例 1：
   *
   * 输入：[1,2,3,4,5]
   * 输出：此列表中的结点 3 (序列化形式：[3,4,5])
   * 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
   * 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
   * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
   * 示例 2：
   *
   * 输入：[1,2,3,4,5,6]
   * 输出：此列表中的结点 4 (序列化形式：[4,5,6])
   * 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
   */
}
